/**
 * @author 13771
 * @date 2021/2/25 14:49
 * @description 动态规划-dp方程  求解金矿问题
 */
public class work3 {
    /**
     * @param g 每座金矿的数量用数组存储
     * @param p 每座金矿开采所需的工人数量用数组存储
     * @param w 参与挖矿的工人总数
     */
    public static int getMostGolds(int[] g,int[] p,int w){
        if (g==null || g.length ==0) return 0;
        if (p==null || p.length ==0) return 0;
        if (g.length != p.length || w <= 0) return 0;

        //创建dp数组,  dp[i][j] 表示 i个金矿 j个工人时的最大收益
        int[][] dp = new int[g.length+1][w+1];

        for (int i = 1; i <= g.length ; i++) {
            for (int j = 1; j <= w; j++) {
                if (p[i-1] > j){
                    dp[i][j]  = dp[i-1][j];
                }else {
                    dp[i][j] = Math.max(dp[i-1][j],g[i-1]+dp[i-1][j-p[i-1]]);
                }
            }
        }
        return dp[g.length][w];
    }

    public static void main(String[] args) {
//        int[] g = {5,4,3,2,1};
//        int[] p = {5,4,3,2,1};

        int[] g = {5000,400,300,200,100};
        int[] p = {11,4,3,2,1};
        int w = 10;
        System.out.println(getMostGolds(g,p,w));
    }

}
